/*
 * Copyright 2010 Michael Nitsche
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package de.mnit.basis.daten.struktur.ordnen.algo;

import de.mnit.basis.daten.konstant.VERHAELTNIS;
import de.mnit.basis.daten.struktur.ordnen.S_Sortierbar;

/**
 * @author Michael Nitsche
 * 26.11.2010	Erstellt
 */
public class Mergesort extends A_SortierAlgo {

	protected void sortieren2(S_Sortierbar<?> tab, int... nach) {
		if(tab.gLaenge()>0) {
			int len=tab.gLaenge();
			int[] dat=new int[len];
			for(int i=1; i<=len; i++)
				dat[i-1]=i;
			teil(tab, nach, dat, 0, len-1);
			tab.sortiereSo(dat);
		}
	}

	private void teil(S_Sortierbar<?> s, int[] nach, int[] dat, int l, int r) {
		if(l==r)
			return;

		int len=r-l+1;
		if(len>2) {
			// Teilen
			int teil=len/2;
			int l1=l;
			int r1=l+teil;
			int l2=r1+1;
			int r2=r;

			teil(s, nach, dat, l1, r1);
			teil(s, nach, dat, l2, r2);

			// Merge
			int p1=l1;
			int p2=l2;
			int pi=0;
			int[] tmp=new int[len];
			while(p1<=r1 || p2<=r2) {
				int i1= p1>r1 ? -1 : dat[p1];
				int i2= p2>r2 ? -1 : dat[p2];
				VERHAELTNIS c= p1>r1
					? VERHAELTNIS.IST_GROESSER
					: p2>r2
						? VERHAELTNIS.IST_KLEINER
						: verhaeltnis(s,i1,i2,nach);
				if(c == VERHAELTNIS.IST_GROESSER) {
					tmp[pi]=i2;
					p2++;
				}
				else {
					tmp[pi]=i1;
					p1++;
				}
				pi++;
			}
			for(int p=0; p<len; p++)
				dat[l+p]=tmp[p];
		}

		// Sort
		else {
			int il=dat[l];
			int ir=dat[r];
			if(verhaeltnis(s,il,ir,nach)==VERHAELTNIS.IST_GROESSER) {
				dat[l]=ir;
				dat[r]=il;
			}
		}
	}

}
